package my.algorithms.sort;

/**
 * Created by IntelliJ IDEA.
 * User: jtruelove
 * Date: 3/12/11
 * Time: 9:29 AM
 * To change this template use File | Settings | File Templates.
 */
public class MergeSort
{
    /**
     * Mergesort algorithm.
     *
     * @param a an array of Comparable items.
     */
    public static void mergeSort(Comparable[] a)
    {
        Comparable[] tmpArray = new Comparable[a.length];
        mergeSort(a, tmpArray, 0, a.length - 1);
    }

    /**
     * Internal method that makes recursive calls.
     *
     * @param a        an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param left     the left-most index of the subarray.
     * @param right    the right-most index of the subarray.
     */
    private static void mergeSort(Comparable[] a, Comparable[] tmpArray,
                                  int left, int right)
    {
        if (left < right)
        {
            // grab the center of the two note this could have issues with buffer overflowing
            int center = (left + right) / 2;
            // break apart the left side
            mergeSort(a, tmpArray, left, center);
            // break apart the right side
            mergeSort(a, tmpArray, center + 1, right);
            // merge them back together
            merge(a, tmpArray, left, center + 1, right);
        }
    }

    /**
     * Internal method that merges two sorted halves of a subarray.
     *
     * @param a        an array of Comparable items.
     * @param tmpArray an array to place the merged result.
     * @param leftPos  the left-most index of the subarray.
     * @param rightPos the index of the start of the second half.
     * @param rightEnd the right-most index of the subarray.
     */
    private static void merge(Comparable[] a, Comparable[] tmpArray,
                              int leftPos, int rightPos, int rightEnd)
    {
        // the end of the left array
        int leftEnd = rightPos - 1;
        // the start of the left array
        int tmpPos = leftPos;
        // the number of elements to merge
        int numElements = rightEnd - leftPos + 1;

        // while the left pos is less than or equal to the left end and the right post is less than or equal to the right end
        while (leftPos <= leftEnd && rightPos <= rightEnd)
        {
            if (a[leftPos].compareTo(a[rightPos]) <= 0)
            {
                // if the left position is smaller set it and move the pointer up
                tmpArray[tmpPos++] = a[leftPos++];
            }
            else
            {
                // if the right position is smaller set it and move the pointer up
                tmpArray[tmpPos++] = a[rightPos++];
            }
        }

        // grab the left overs and copy them
        while (leftPos <= leftEnd)    // Copy rest of first half
        {
            tmpArray[tmpPos++] = a[leftPos++];
        }

        // grab the left overs and copy them
        while (rightPos <= rightEnd)  // Copy rest of right half
        {
            tmpArray[tmpPos++] = a[rightPos++];
        }

        // Copy tmpArray back
        for (int i = 0; i < numElements; i++, rightEnd--)
        {
            a[rightEnd] = tmpArray[rightEnd];
        }
    }
}
